package 我的Java学习_算法基础.day_08;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @date 2021/8/23 - 08 - 23 - 14:59
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _125_区间选点 {
    /**
     * 给出多个区间，每个区间给出需求点数
     * 求满足需求的最小点数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n  = sc.nextInt();
        Interval[] intervals = new Interval[n];
        for (int i = 0; i < n; i++) {
            intervals[i]=new Interval(sc.nextInt(),sc.nextInt(),sc.nextInt());
        }
        Arrays.sort(intervals);
        int right = intervals[n-1].end;
        flag = new int[right+1]; //辅助数组,标记数轴上的点是否被选中
        findMinPointCount(intervals);
    }
    static int[] flag;  //辅助数组，数轴上打上点处标记为1
    private static void findMinPointCount(Interval[] intervals){
        for (int i = 0; i < intervals.length; i++) {
            //查阅区间中有多少个已经标记的点
            int begin = intervals[i].begin;
            int end = intervals[i].end;
            int pointCount = sum(flag,begin,end);//区间中已选点的数量
            //如果标记点不够，从区间右端开始标记，遇到标记过的跳过
            intervals[i].pointCount-= pointCount;//需要新增标记点的数量
            while(intervals[i].pointCount>0){
                if(flag[end]==0){
                    flag[end]=1;
                    intervals[i].pointCount--;
                }
                end--;
            }
        }
        System.out.println(sum(flag,0,flag.length-1));
    }
    private static int sum(int[] a,int begin,int end){
        int sum = 0;
        for(int i =begin;i<=end;i++){
            sum+=a[i];
        }
        return sum;
    }
    private static class Interval implements Comparable<Interval>{
        int begin;
        int end;
        int pointCount;

        public Interval(int begin, int end, int pointCount) {
            this.begin = begin;
            this.end = end;
            this.pointCount = pointCount;
        }

        @Override
        public int compareTo(Interval o) {
            int t = this.end - o.end;
            if(t==0)
                return this.begin - o.begin;
            else
                return t;
        }
    }
}
